import java.io.Serializable;


public class MagicDiamonds {
	
	public static class FFBitSet implements Serializable {
		/**
		 * 
		 */
		private static final long serialVersionUID = 4857979165670395249L;
		
		public static final int SHIFT = 5;
		public static final int CHUNKSIZE = 1 << SHIFT;
		public static final int CHUNKMASK = CHUNKSIZE - 1;	
		private final int size;	
		private final int[] chunks;	
		
		public FFBitSet(final int size) {
			assert size >= 0;
			this.size = size;
			chunks = new int[(size+CHUNKSIZE-1)/CHUNKSIZE];		
			//System.out.println(String.format("Created BigSet with size: %d length: %d", size, nchunks));
		}
			
		
		public final void set(final int bit) {
			chunks[bit >> SHIFT] |= (1 << (bit & CHUNKMASK));
		}
		
		public final void unset(final int bit) {
			chunks[bit >> SHIFT] ^= (1 << (bit & CHUNKMASK));
		}
		
		public final boolean get(final int bit) {
			return (chunks[bit >> SHIFT] & (1 << (bit & CHUNKMASK))) != 0;
		}


		public int getSize() {
			return size;
		}
		
		
	}
	public final static int[] erathosphen(int max) {
		assert max > 0;
		int n = 0;
		
		FFBitSet bitSet = new FFBitSet(max + 1); //don't count 0 and 1
		int i;		
		
		for (i = 2; i <= (int) Math.sqrt(max); i++) {
			//opcount++;
			if (!bitSet.get(i)) {
				n++;
				for (int j = i*i; j <= max; j += i) {
					bitSet.set(j);
					//opcount ++;
				}
			}
		}
		for (; i <= max; i++) {
			//opcount++;
			if (!bitSet.get(i)) {
				n++;
			}
		}

		int[] res = new int[n];
		int cur = 0;
		for (i = 2; i <= max; i++) {
			if (!bitSet.get(i)) {
				res[cur++] = i;
			}
		}

		return res;
	}
	
	
	public long minimalTransfer(long n) {
		if (n == 3) return 3;
		if (n == 2) return 2;
		if (n == 1) return 1;
		
		int[] primes = erathosphen((int)(Math.sqrt(n) + 2));
		for (int x: primes) {
			if (n % x == 0) {
				return 1;
			}
		}
		return 2;
	}
		
}
